An Adaptive Algorithm for Vector Partitioning

The vector partition problem concerns the partitioning of a set A of n vectors in d-space into p parts so as to maximize an objective function c which is convex on the sum of vectors in each part. Here all parameters d, p, n are considered variables. In this paper, we study the adjacency of vertices in the associated partition polytopes. Using our adjacency characterization for these polytopes, we are able to develop an adaptive algorithm for the vector partition problem that runs in time O(q(L)v) and in space O(L), where q is a polynomial function, L is the input size and v is the number of vertices of the associated partition polytope. It is based on an output-sensitive algorithm for enumerating all vertices of the partition polytope. Our adjacency characterization also implies a polynomial upper bound on the combinatorial diameter of partition polytopes. We also establish a partition polytope analogue of the lower bound theorem, indicating that the output-sensitive enumeration algorithm can be far superior to previously known algorithms that run in time polynomial in the size of the worst-case output.     

Uniqueness and asymptotic behaviour for solutions of semilinear problems with boundary blow-up

In this paper we prove uniqueness of positive solutions to logistic singular problems , , 1$">, 0$"> in , where the main feature is the fact that . More importantly, we provide exact asymptotic estimates describing, in the form of a two-term expansion, the blow-up rate for the solutions near . This expansion involves both the distance function and the mean curvature of .

     

Mixed Partitions of Projective Geometries

Starting from a linear collineation of PG(2n–1,q) suitably constructed from a Singer cycle of GL(n,q), we prove the existence of a partition of PG(2n–1,q) consisting of two (n–1)-subspaces and caps, all having size (qⁿ–1)/(q–1) or (qⁿ–1)/(q+1) according as n is odd or even respectively. Similar partitions of quadrics or hermitian varieties into two maximal totally isotropic subspaces and caps of equal size are also obtained. We finally consider the possibility of partitioning the Segre variety of PG(8,q) into caps of size q²+q+1 which are Veronese surfaces.     

Powers of Euler's Product and Related Identities

Ramanujan's partition congruences can be proved by first showing that the coefficients in the expansions of (q; q) ^r satisfy certain divisibility properties when r = 4, 6 and 10. We show that much more is true. For these and other values of r, the coefficients in the expansions of (q; q) ^r satisfy arithmetic relations, and these arithmetic relations imply the divisibility properties referred to above. We also obtain arithmetic relations for the coefficients in the expansions of (q; q) ^r (q ^t; q ^t) ^s , for t = 2, 3, 4 and various values of r and s. Our proofs are explicit and elementary, and make use of the Macdonald identities of ranks 1 and 2 (which include the Jacobi triple product, quintuple product and Winquist's identities). The paper concludes with a list of conjectures.     

氧化亚氮3000—0200和1001—0110跃迁带在高温下的线强度

采用乘积近似法计算了氧化亚氮分子的总配分函数，其中转动配分函数考虑了离心扭曲修正，振动配分函数采用谐振子近似. 利用计算所得的配分函数和实验振动跃迁矩平方及Herman-Wallis因子系数，计算了氧化亚氮3000—0200和1001—0110跃迁带在常温和高温下的线强度. 结果显示，当温度高达3000K时，计算所得线强度与实验值及HITRAN数据库提供的结果仍符合较好. 这表明高温下的分子配分函数和线强度的计算是可靠的. 还进一步计算了氧化亚氮3000—0200和1001—0110跃迁带在更高温度(40 关键词： 氧化亚氮 配分函数 线强度 高温     

Balanced decomposition of a vertex-colored graph

A balanced vertex-coloring of a graph G is a function c from V(G) to {−1,0,1} such that ∑{c(v):v∈V(G)}=0. A subset U of V(G) is called a balanced set if U induces a connected subgraph and ∑{c(v):v∈U}=0. A decomposition V(G)=V₁∪?∪V_r is called a balanced decomposition if V_i is a balanced set for 1≤i≤r.In this paper, the balanced decomposition number f(G) of G is introduced; f(G) is the smallest integer s such that for any balanced vertex-coloring c of G, there exists a balanced decomposition V(G)=V₁∪?∪V_r with |V_i|≤s for 1≤i≤r. Balanced decomposition numbers of some basic families of graphs such as complete graphs, trees, complete bipartite graphs, cycles, 2-connected graphs are studied.     

Set Partition Complexes

The Hom complexes were introduced by Lovász to study topological obstructions to graph colorings. The vertices of Hom(G,K _n ) are the n-colorings of the graph G, and a graph coloring is a partition of the vertex set into independent sets. Replacing the independence condition with any hereditary condition defines a set partition complex. We show how coloring questions arising from, for example, Ramsey theory can be formulated with set partition complexes. It was conjectured by Babson and Kozlov, and proved by Čukić and Kozlov, that Hom(G,K _n ) is (n−d−2)-connected, where d is the maximal degree of a vertex of G. We generalize this to set partition complexes.     

Amalgamation of partitions from multiple segmentation bases: A comparison of non-model-based and model-based methods

The segmentation of customers on multiple bases is a pervasive problem in marketing research. For example, segmentation service providers partition customers using a variety of demographic and psychographic characteristics, as well as an array of consumption attributes such as brand loyalty, switching behavior, and product/service satisfaction. Unfortunately, the partitions obtained from multiple bases are often not in good agreement with one another, making effective segmentation a difficult managerial task. Therefore, the construction of segments using multiple independent bases often results in a need to establish a partition that represents an amalgamation or consensus of the individual partitions. In this paper, we compare three methods for finding a consensus partition. The first two methods are deterministic, do not use a statistical model in the development of the consensus partition, and are representative of methods used in commercial settings, whereas the third method is based on finite mixture modeling. In a large-scale simulation experiment the finite mixture model yielded better average recovery of holdout (validation) partitions than its non-model-based competitors. This result calls for important changes in the current practice of segmentation service providers that group customers for a variety of managerial goals related to the design and marketing of products and services.     

A major index for matchings and set partitions

We introduce a statistic pmaj(P) for partitions of [n], and show that it is equidistributed with cr₂, the number of 2-crossings, over all partitions of [n] with given sets of minimal block elements and maximal block elements. This generalizes the classical result of equidistribution for the permutation statistics inv and maj.     

Computing finest mincut partitions of a graph and application to routing problems

Let G=(V,E,w) be an n-vertex graph with edge weights w>0. We propose an algorithm computing all partitions of V into mincuts of G such that the mincuts in the partitions cannot be partitioned further into mincuts. There are O(n) such finest mincut partitions. A mincut is a non-empty proper subset of V such that the total weight of edges with exactly one end in the subset is minimal. The proposed algorithm exploits the cactus representation of mincuts and has the same time complexity as cactus construction. An application to the exact solution of the general routing problem is described.